package org.common.utils.hash;
import java.util.Map;
import java.util.TreeMap;

/**
 * 哈希一致实现
 */
public final class ConsistentHash<T> {
    /**
     * 节点
     */
    private final TreeMap<Integer, T> circle = new TreeMap<>();
    /**
     * 虚拟节点数
     */
    private final int virtualCount;

    public ConsistentHash() {
         this(128);
    }

    public ConsistentHash(int virtualCount) {
        this.virtualCount = virtualCount;
    }

    public void add(T node) {
        for (int i = 0; i < virtualCount; i++) {
            int hash = hash(node.hashCode() + "#" + i);
            circle.put(hash, node);
        }
    }

    public void remove(T node) {
        for (int i = 0; i < virtualCount; i++) {
            int hash = hash(node.hashCode() + "#" + i);
            circle.remove(hash);
        }
    }

    public T get(String key) {
        if (circle.isEmpty()) {
            return null;
        }
        int hash = hash(key);
        if (!circle.containsKey(hash)) {
            Map.Entry<Integer, T> entry = circle.ceilingEntry(hash);
            hash = entry == null? circle.lastKey() : entry.getKey();
//            SortedMap<Integer, T> tailMap = circle.tailMap(hash);
//            hash = tailMap.isEmpty()? circle.firstKey() : tailMap.firstKey();
        }
        return circle.get(hash);
    }

    private int hash(String key) {
        // 使用 FNV1_32_HASH 算法计算哈希值
        final int p = 16777619;
        int hash = (int) 2166136261L;
        for (int i = 0; i < key.length(); i++) {
            hash = (hash ^ key.charAt(i)) * p;
        }
        hash += hash << 13;
        hash ^= hash >> 7;
        hash += hash << 3;
        hash ^= hash >> 17;
        hash += hash << 5;
        return hash;
    }
}